Minimal-interval semantics associates with each query over a document a setof intervals, called witnesses, that are incomparable with respect to inclusion(i.e., they form an antichain): witnesses define the minimal regions of thedocument satisfying the query. Minimal-interval semantics makes it easy todefine and compute several sophisticated proximity operators, provides snippetsfor user presentation, and can be used to rank documents. In this paper weprovide algorithms for computing conjunction and disjunction that are linear inthe number of intervals and logarithmic in the number of operands; foradditional operators, such as ordered conjunction and Brouwerian difference, weprovide linear algorithms. In all cases, space is linear in the number ofoperands. More importantly, we define a formal notion of optimal laziness, andeither prove it, or prove its impossibility, for each algorithm. We cast ourresults in a general framework of antichains of intervals on total orders,making our algorithms directly applicable to other domains.
展开▼
